package com.ds.sort.impl;

import java.util.Random;

import com.ds.sort.MySort;

public class ShellSort implements MySort {

	
	public <T extends Comparable<? super T>> void  sort(T[] t){
		
		int[] steps = {109,41,19,5,1};
		
		for(int step : steps) {
			System.out.println("step : " + step);
			if(step > t.length) {
				continue;
			}
			
			for(int i = 0;i < step;i++) {
				for(int j = i + step;j < t.length;j = j + step) {
					
					T temp = t[j];
					int k;
					for(k = j;k - step >= 0 && temp.compareTo(t[k - step]) < 0;k -= step) {
						t[k] = t[k - step];
					}
					t[k] = temp;
				}
			}
		}
	}
	
	public <T extends Comparable<? super T>> void  sort2(T[] t) {
		
		int[] steps = {109,41,19,5,1};
		for(int step : steps) {
			
			for(int i = step; i < t.length; i++) {
				
				T temp = t[i];
				int j;
				for(j = i;j - step >= 0 && temp.compareTo(t[j - step]) < 0; j -= step) {
					t[j] = t[j - step];
				}
				t[j] = temp;
				
			}
			
		}
	}
}
